import random
import time
import sys
from operator import itemgetter ,attrgetter
sys.setrecursionlimit(10000000)#增加递归的深度
class sort:
    def __init__(self,n,nums_range):
        self.n=n
        self.arr=[]
        self.nums_range=nums_range
        self.random_nums()
    def random_nums(self):
        for i in range(self.n):
            self.arr.append(random.randint(0,self.nums_range-1))


    def partition(self,left,right):
        arr=self.arr
        k=left
        for i in range(left,right):
            if arr[i]<arr[right]:
                arr[i],arr[k]=arr[k],arr[i]
                k+=1
        arr[k].arr[right]=arr[right].arr[k]
        return k

    def quick_sort(self,left,right):
          if left<right:
              pivot=self.partition(left,right)
              self.quick_sort(left,pivot-1)
              self.quick_sort(pivot+1,right)

    def adjust_max_heap(self,parent_pos,arr_len):
        '''
        把某一颗字数调整为最大堆

        :param parent_pos:
        :param arr_len:
        :return:
        '''
        arr=self.arr
        dad=parent_pos
        son=2*dad+1
        while son<arr_len:
            if son+1<arr_len and arr[son]<arr[son+1]:#如果有右孩子，并且右孩子大于左孩子，则son指向右孩子
                son+=1
            if arr[dad]<arr[son]:#如果父节点小于子节点，则交换父子节点
                arr[dad],arr[son]=arr[son],arr[dad]
                dad=son
                son=2*dad+1
            else:
                break
    def heap_sort(self):
        arr=self.arr
        #把列表调整为大根堆，从最后一个非叶子节点开始调整
        for parent_pos in range(self.n//2-1,-1,-1):
            self.adjust_max_heap(parent_pos,self.n)
        for end_pos in range(self.n-1,0,-1):
            arr[end_pos],arr[0]=arr[0],arr[end_pos]
            self.adjust_max_heap(0,end_pos)

    def cal_time(self,sort_func,*args,**kwargs):
        '''
        计算排序时间，sort_func就是传递一种行为
        :param sort_func:
        :param args:
        :param kwargs:
        :return:
        '''
        start=time.time()
        sort_func(*args,**kwargs)#回调函数
        end=time.time()
        print(f'所用时间为{end-start}')

    # def cal_time(self,sort_func,args,**kwargs):
    #     '''
    #     计算排序时间
    #     :param sort_func:
    #     :return:
    #     '''
    #     start=time.time()#距离1970年1月1号
    #     sort_func()
    #     end=time.time(*args,**kwargs)
    #     print(f'使用的排序时间为{end-start}')
if __name__=='__main__':
    s=sort(10,10)
    s.heap_sort()
    print(s.arr)
    print("*"*100)
    # s.cal_time(s.quick_sort,0,s.n-1)
    # print(s.arr)
    list1=[1,3,2,4,5,2,3]
    print(sorted(list1))#sorted不会影响原来的队列
    print(list1)
    print("*"*100)
    # 字典也可以使用sorted，根据键值对中的键进行排序
    print(sorted({5:'0',2:'b',3:'c'}))
    str_list = "This is a test string from Andrew".split()
    print(str_list)
    # 字符串可以根据ASCII码进行排序
    print(sorted(str_list))
    print("*" * 100)
    def str_lower(str1):
        '''
        比较规则函数
        :param str1:
        :return:
        '''
        return str1.lower()
    print(sorted(str_list,key=str_lower))


student_tuples=[
    ('john','a',15),
    ('jane','b',12),
    ('dave','b',10)
]
print("="*100)
print(type(student_tuples))
print("="*100)
class student:
    def __init__(self,name,grade,age):
        self.name=name
        self.grade=grade
        self.age=age
    def __repr__(self):
        '''
        类似于str,repr可以返回其他类型,一般是元组类型
        :return:
        '''
        return repr((self.name,self.grade,self.age))

student_object={
    student('john','a',15),
    student('jane','b',12),
    student('dave','b',10)
}
print(type(student_object))
print(sorted(student_object,key=lambda student:student.age))
#匿名函数，函数在当前位置只使用一次，不需要再其他地方再次调用
#lambda表达式就是匿名函数
# print(sorted(student_tuples,key=lambda x:x[2]))
#用于元组或者列表
print(sorted(student_tuples,key=itemgetter(1)))
#用于对象
print(sorted(student_object ,key=attrgetter('age')))
#多个对象排序
print(sorted(student_tuples,key=itemgetter(1,2)))
print(sorted(student_object,key=attrgetter('age','grade')))
print(sorted(student_tuples,key=lambda x:x[1:]))
mydict={'li':['m',6],'zhang':['p',3]}
for v in mydict.items():
    print(v)
print(sorted(mydict.items(),key=lambda v:v[1][1]))
